#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<Windows.h>
typedef struct LNode* PtrToLNode;
typedef int ElementType;
struct LNode {
	ElementType Data1, Data2;
	PtrToLNode Next;
};
typedef PtrToLNode List;
List makeEmpty() {
	List L = (List)malloc(sizeof(struct LNode));
	L->Next = NULL;
	return L;
}
int Length(List L) {
	List p = L->Next;
	int cut = 0;
	while (p != NULL) {
		cut++;
		p = p->Next;
	}
	return cut;
}
void Findkth(List L, int k) {
	List p = L->Next;
	int cnt = 1;
	while (p != NULL && cnt < k) {
		p = p->Next;
		cnt++;
	}
	if (cnt == k) {
		printf("第%d个元素为：", k);
		if (p->Data2 == 0)printf("%d\n", p->Data1);
		else printf("%dX^%d\n", p->Data1, p->Data2);
	}
	else 
		printf("在链表中没有第%d个元素\n", k);
}
List Find(List L, ElementType x) {
	List p = L->Next;
	while (p && p->Data2 != x) p = p->Next;
	if (p)return p;
	else return NULL;
}
List Insert(List L, ElementType x, ElementType y, int i) {
	List tmp = (List)malloc(sizeof(struct LNode));
	tmp->Data1 = x; tmp->Data2 = y;
	int cnt = 0;
	List p = L;
	while (p && cnt < i - 1) {
		p = p->Next;
		cnt++;
	}
	if (p == NULL || cnt != i - 1) 
		printf("插入位置的参数错误\n!");
	else {
		tmp->Next = p->Next;
		p->Next = tmp;
	}
	return L;
}
List Delete(List L, int i) {
	List tmp, p = L;
	int cnt = 0;
	while (p && cnt < i - 1) {
		p = p->Next;
		cnt++;
	}
	if (p == NULL || cnt != i - 1 || p->Next == NULL)printf("删除位置参数错误！\n");
	else {
		tmp = p->Next;
		p->Next = tmp->Next;
		free(tmp);
	}
	return L;
}
void print(List L) {
	if (L->Next == NULL) {
		printf("0\n");
		return;
	}
	List p = L->Next;
	if (p->Data1 != 0) printf("%d*X^%d", p->Data1, p->Data2);
	else printf("0");
	p = L->Next->Next;
	while (p != NULL) {
		if (p->Data1 == 0) {
			p = p->Next;
			continue;
		}
		if (p->Data1 == 1) {
			if (p->Data2 == 0) {
				if (p->Data1 < 0) printf("%d", p->Data1);
				else printf("+%d", p->Data1);
			}
			else if (p->Data2 == 1) {
				if (p->Data1 < 0)printf("X");
				else printf("+X", p->Data1);
			}
			else {
				if (p->Data1 < 0)printf("X^%d", p->Data1, p->Data2);
				else printf("+X^%d", p->Data1, p->Data2);
			}
		}
		else {
			if (p->Data2 == 0) {
				if (p->Data1 < 0) printf("%d", p->Data1);
				else printf("+%d", p->Data1);
			}
			else if(p->Data2==1){
				if (p->Data1 < 0)printf("%d*X", p->Data1);
				else printf("+%d*X", p->Data1);
			}
			else {
				if (p->Data1 < 0)printf("%d*X^%d", p->Data1, p->Data2);
				else printf("+%d*X^%d", p->Data1, p->Data2);
			}
		}
		p = p->Next;
	}
	printf("\n");
}
List List_sort(List L) {
	if (L->Next == NULL)return L;
	List p, q;
	p = L->Next;
	int i = 0;
	for (p = L->Next; p!= NULL; p = p->Next) 
		for (q = p->Next; q!= NULL; q = q->Next) 
			if (p->Data2 < q->Data2) {
				ElementType t = p->Data2;
				p->Data2 = q->Data2;
				q->Data2 = t;
				t = p->Data1;
				p->Data1 = q->Data1;
				q->Data1 = t;
			}
	return L;
}
List add(List a, List b) {
	List p = b->Next;
	while (p != NULL) {
		List q = a->Next;
		int flag = 0;
		while (q != NULL) {
			if (p->Data2 == q->Data2) {
				q->Data1 += p->Data1;
				flag = 1;
			}
			q = q->Next;
		}
		if (flag == 0)Insert(a, p->Data1, p->Data2, Length(a) + 1);
		p = p->Next;
	}
	return a;
}
#include<stdio.h> 
List Multiplication(List a, List b) {
	List c = makeEmpty();
	List p = a->Next;
	List d = c;
	while (p != NULL) {
		List q = b->Next;
		while (q != NULL) {
			List s = (List)malloc(sizeof(struct LNode));
			s->Data1 = p->Data1 * q->Data1;
			s->Data2 = p->Data2 + q->Data2;
			d->Next = s;
			s->Next = NULL;
			d = s;
			q = q->Next;
		}
		p = p->Next;
	}
	return c;
}
List new_List_sort(List L) {
	List p = L->Next;
	while (p != NULL) {
		List q = p->Next;
		while (q != NULL) {
			if (p->Data2 == q->Data2) {
				p->Data1 += q->Data1;
				q->Data1 = 0;
			}
			q = q->Next;
		}
		p = p->Next;
	}
	return L;
}
int main() {
	List a = makeEmpty();
	List b = makeEmpty();
	int na, nb;
	printf("请分别输入多项式a与多项式b的非0系数的个数：\n");
	scanf("%d %d", &na, &nb);
	printf("请输入多项式a的各项系数与指数：\n");
	ElementType x, y;
	if (na != 0) {
		while (na--) {
			scanf("%d %d", &x, &y);
			a = Insert(a, x, y, Length(a) + 1);
		}
	}
	if (nb != 0) {
		printf("请输入多项式b的各项系数与指数：\n");
		while (nb--) {
			scanf("%d %d", &x, &y);
			b = Insert(b, x, y, Length(b) + 1);
		}
	}
	List c = Multiplication(a, b);
	List_sort(c);
	new_List_sort(c);
	printf("两个多项式相乘后得到的结果为：\n");
	print(c);
	return 0;
}